#define _CRT_SECURE_NO_WARNINGS
class Solution {
public:
    void backTrace(vector<vector<int>>& vv, vector<int>& v, int& k, int& n, int start)
    {
        if (k == 0)
        {
            if (n == 0)
                vv.push_back(v);
            return;
        }
        for (int i = start; i <= 9; i++)
        {
            if (n <= 0)
                break;
            v.push_back(i);
            n -= i;
            k--;
            backTrace(vv, v, k, n, i + 1);
            v.pop_back();
            n += i;
            k++;
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> vv;
        vector<int> v;
        backTrace(vv, v, k, n, 1);
        return vv;
    }
};

class Solution {
public:
    vector<string> number2letter = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
    void getletter(vector<string>& ret, string& s, int& k, string& digits, int start)
    {
        if (k == 0)
        {
            ret.push_back(s);
            return;
        }
        for (int i = start; i < digits.size(); i++)
        {
            for (int j = 0; j < number2letter[digits[i] - '0'].size(); j++)
            {
                s += number2letter[digits[i] - '0'][j];
                k--;
                getletter(ret, s, k, digits, i + 1);
                s.pop_back();
                k++;
            }
        }
    }
    vector<string> letterCombinations(string digits) {
        vector<string> ret;
        if (digits.size() == 0)
            return ret;
        string s;
        int k = digits.size();
        getletter(ret, s, k, digits, 0);
        return ret;
    }
};